package cn.lwp.algorithm.examples1;

import java.util.*;

/**
 * @Author lanwp
 * @Date 2019/3/21
 *
 * 字符串的排列
 *
 * 题目：输入一个字符串，打印出该字符串中字符的所有排列。
 *
 * 例如输入字符串abc，则输出由字符a、b、c 所能排列出来的所有字符串abc、acb、bac、bca、cab 和cba。
 *
 * 分析：这是一道很好的考查对递归理解的编程题。
 */
public class StringAllArrangedTest {

    private static Set<String> set = new TreeSet<>();

    public static void main(String[] args) {
        System.out.println(permutationCount("abcd"));
        String inputString = "abc";
        permutation(inputString.toCharArray(), 0, inputString.toCharArray().length - 1);
        System.out.println("************");
        Iterator<String> iterator = set.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

    }

    public static void swap(char[] chars, int a, int b)
    {
        char tmp = chars[a];
        chars[a] = chars[b];
        chars[b] = tmp;
    }

    public static void permutation(char[] chars, int start, int end) {
        if (start == end) {
            //递归出口：只剩一个字符，即无法交换
            set.add(String.valueOf(chars));
            System.out.println(String.valueOf(chars));
        } else {
            for (int i = start; i < chars.length; i++){
                //依次交换n与它后边的每一个字符
                swap(chars, i, start);
                permutation(chars, start + 1, end);
                swap(chars, start, i);
            }
        }
    }


    /**
     * 字符串全排列的字符串数量
     * @return
     */
    public static long permutationCount(String str) {
        if (str == null || str.isEmpty()) {
            return 0;
        }
        long count = 1;
        for (int i = 1; i <= str.length(); i++) {
            count *= i;
        }
        return count;
        // 1 2 6 24 120
    }


}
